package Hot_100;

import java.util.Scanner;

//删除链表倒数第n个节点
public class Hot_100_19 {
    public static class ListNode {
        int val;
        ListNode next;

        public ListNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ListNode head = new ListNode(-1);
        System.out.print("请输入链表节点个数: ");
        int m = sc.nextInt();
        System.out.print("请输入链表节点值: ");
        head = Create(m);
        System.out.println();
        System.out.print("请输入要删除倒数第几个节点: ");
        int n = sc.nextInt();
        System.out.println();
        head = removeNthFromEnd(head, n);
        System.out.print("结果: ");
        Print(head);
    }

    /**
     * 创建链表函数
     *
     * @param n
     * @return
     */
    public static ListNode Create(int n) {
        Scanner sc = new Scanner(System.in);
        //定义投节点
        ListNode head = new ListNode(-1);
        ListNode p = head, q = head;
        //给头节点赋值
        p.val = sc.nextInt();
        n--;
        //依次赋值，形成链
        while (n > 0) {
            q = p;
            p = new ListNode(-1);
            p.val = sc.nextInt();
            q.next = p;
            n--;
        }
        return head;
    }

    /**
     * 删除倒数第n个节点
     *
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode pre = new ListNode(-1);
        ListNode fast = pre, slow = pre;
        pre.next = head;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return pre.next;
    }

    /**
     * 输出链表元素函数
     *
     * @param head
     */
    public static void Print(ListNode head) {
        for (ListNode p = head; p != null; p = p.next) {
            System.out.print(p.val + " ");
        }
    }
}
//时间复杂度: O(n)
//空间复杂度: O(1)